package code2301_2400.code20_30;

/**
 * 给定一个排序的整数数组 nums 和一个整数目标值 target ，请在数组中找到 target ，并返回其下标。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 *
 * 请必须使用时间复杂度为 O(log n) 的算法。
 *
 * 输入: nums = [1,3,5,6], target = 5
 * 输出: 2
 *
 * 输入: nums = [1,3,5,6], target = 2
 * 输出: 1
 *
 * 输入: nums = [1,3,5,6], target = 7
 * 输出: 4
 *
 * 输入: nums = [1,3,5,6], target = 0
 * 输出: 0
 *
 * 输入: nums = [1], target = 0
 * 输出: 0
 */
public class _2322_Offer68_searchInsert {

    /**
     * 执行用时：     * 0 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 38.1 MB     * , 在所有 Java 提交中击败了     * 43.20%     * 的用户
     * @param nums
     * @param target
     * @return
     */
    public int searchInsert(int[] nums, int target) {
        int right = nums.length-1;
        int left = 0;
        int mid;
        while (left <= right){
            mid = left + (right - left)/2;
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]>target){
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return left;
    }

}
